package com.tys.algorithm.advanced.test.class38;

/**
 * 定义一种数，可以表示成若干（数量>1)连续正数和的数
 * 比如：
 * 5 = 2 + 3，5 就是这样的数
 * 12 = 3 + 4 + 5，12就是这样的数
 * 1不是这样的数，因为要求数量大于1个，连续正数和
 * 2 = 1 + 1，2 也不是，因为等号右边不是连续正数
 * 给定一个参数N，返回是不是可以表示成若干连续正数和的数
 */
public class Code03_MSumToN {
    //方法1：
    public static boolean isMSum1(int num) {
        //从1开始累加
        for (int start = 1; start <= num; start++) {
            int sum = start;
            //累加看是否满足条件：累加到num
            for (int j = start + 1; j <= num; j++) {
                //累加大于num找不到答案退出
                if (sum + j > num) {
                    break;
                }
                //相等找到答案
                if (sum + j == num) {
                    return true;
                }
                //累加
                sum += j;
            }
        }
        return false;
    }

    //方法2：规律：2的某次方返回false，其他true
    public static boolean isMSum2(int num) {
//		//num & (~num+1) num最右侧的1，和num相等则num是2的某次方
//		return num == (num & (~num + 1));
//		
//		return num == (num & (-num));
//		
//		//num只有一个位上有1： num & （num-1) 是0
        //num有多个1，则 num & （num-1)不是0
        return (num & (num - 1)) != 0;
    }

    public static void main(String[] args) {
        for (int num = 1; num < 200; num++) {
            System.out.println(num + " : " + isMSum1(num));
        }
        System.out.println("test begin");
        for (int num = 1; num < 5000; num++) {
            if (isMSum1(num) != isMSum2(num)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("test end");

    }
}
